package com.lun.swordtowardoffer2.c15;

import java.util.LinkedList;
import java.util.Queue;

public class UpdateMatrix {
	public int[][] updateMatrix(int[][] matrix){
		int rows = matrix.length;
		int cols = matrix[0].length;
		
		int[][] result = new int[rows][cols];
		Queue<int[]> queue = new LinkedList<>();
		
		for(int i = 0; i < rows; i++) {
			for(int j = 0; j < cols; j++) {
				if(matrix[i][j] == 0) {
					queue.offer(new int[] {i, j});
					result[i][j] = 0;
				}else {
					result[i][j] = Integer.MAX_VALUE;
				}
			}
		}
		
		int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
		
		while(!queue.isEmpty()) {
			int[] pos = queue.poll();
			int dis = result[pos[0]][pos[1]];
			for(int[] dir : directions) {
				int r = pos[0] + dir[0];
				int c = pos[1] + dir[1];
				
				if(-1 < r && r < rows &&//
						-1 < c && c < cols) {
					if(dis + 1 < result[r][c]) {
						result[r][c] = dis + 1;
						queue.offer(new int[] {r, c});
					}
				}
			}
		}
		
		return result;
	}
}
